1. Field of the Invention
The invention relates to Asynchronous Transfer Mode communications devices. More particularly, the invention relates to methods and apparatus for buffering ATM cells, particularly during multicasting.
2. State of the Art
ATM, by nature, is xe2x80x9cburstyxe2x80x9d. Consequently, buffers must be provided in ATM devices so that cell loss is minimized. If one buffer is shared by more than one physical destination (PHY), an adverse effect known as xe2x80x9chead of line blockingxe2x80x9d can occur. Head of line blocking occurs when a cell at the head of a buffer cannot be transmitted to its PHY because of any number of reasons. This cell then blocks the transmission of all of the cells behind it. Head of line blocking can be avoided by providing separate buffers for each PHY in an ATM device. However, this can be costly and space consuming.
In an ATM network, it is often desirable to effect a multicast of ATM cells; i.e., to transport ATM cells from a source terminal to a plurality of different destinations. Each of the destinations of the multicast will typically have its own address. Thus, it is necessary to duplicate the ATM cells, provide different headers for each of the cells, and send the cells out on different virtual circuits (VCs). The different VCs may be located at different PHYs in the case of a spatial multicast or the same PHY in the case of a logical multicast. In the case of spatial multicast, extensive buffering may be necessary in order to accommodate all of the copies of each incoming multicast cell. It will be appreciated that the outgoing buffers will rapidly fill with copies of each single incoming multicast cell. In order to reduce the amount of buffer space required for multicasting, it is known to use a single buffer for multicast incoming cells and to replicate the cells just as they are ready to be transmitted out of the switch. Although this saves buffer space, it makes head of line blocking a more likely occurrence.
It is therefore an object of the invention to provide methods and apparatus for preventing head of line blocking in an ATM device.
It is also an object of the invention to provide methods and apparatus for preventing head of line blocking in an ATM device which do not require extensive use of buffer memory.
In accord with these objects which will be discussed in detail below, the apparatus of the present invention includes a UTOPIA interface, a scheduler, at least one multicast queue, at least one unicast queue, a multicast session table, a multicast timer, and a problem PHY vector. The methods of the invention include alternate scheduling between multicast queue(s) and unicast queue(s). In particular, the PHY devices are serviced in round robin or other fair scheduling order. According to first embodiment, which is not the presently preferred embodiment, as each PHY is serviced, it is determined whether there exists a unicast cell or a multicast cell or both for this PHY. If both unicast and multicast cells are scheduled for this PHY, scheduling is alternated between them. If only unicast or multicast cells are scheduled for this PHY, alternation is not necessary.
For purposes of this invention, the act of replicating a multicast cell to plural PHY destinations is referred to as a multicast xe2x80x9csessionxe2x80x9d and the identities of the PHY destinations are stored in a multicast session table for each session. The copying of the cell to one of the PHYs in the multicast session is referred to as a xe2x80x9cleafxe2x80x9d in the session. According to the first embodiment, a multicast timer is started when a multicast cell reaches the head of the multicast queue. The timer is a count down timer preferably based on the slowest PHY device. If a PHY device in a session is inactive, it is skipped and the next PHY in the session is serviced. The session ends when one of three events occurs: all PHYs in the session table have been serviced, the timer expires, or the only PHYs remaining in the session are PHYs listed in the problem PHY vector. At the end of each multicast session, the problem PHY vector is updated. The problem PHY vector includes a list of all of the PHYs which are deemed to be presently inactive based on the last multicast session and all previous multicast sessions. The problem PHY vector is updated whenever an inactive PHY becomes active, either in a unicast or a multicast cell transfer. The problem PHY vector is preferably used to shorten the multicast session before the timer expires. It may also be used by an external device to modify multicast session tables.
According to a second and presently preferred embodiment of the invention, the servicing of PHYs is driven by the status of the queues. In a background process, the status of the unicast and multicast queue is repeatedly updated. The status of PHYs is obtained through the UTOPIA interface. If the multicast queue is not empty and the last queue serviced was a unicast queue, the multicast queue is serviced by copying the head of line cell to the next active PHY in the multicast session (i.e. the next leaf of the session). If the multicast queue is empty or if the last cell serviced was not a unicast cell, the next (in round robin) available unicast queue is serviced. As used herein, xe2x80x9cavailable unicast queuexe2x80x9d means a queue with a cell ready to be sent to an active PHY which is not part of the current multicast session. During the multicast session, if the only PHYs remaining in the session table are PHYs which are in the problem PHY vector, the session is ended and the problem PHY vector is updated. If the only PHYs remaining in the multicast session include inactive PHYs which are not in the problem PHY vector, the multicast timer is started. The scheduler continues to attempt to complete the multicast session until the timer expires or until the only PHYs left are in the problem PHY vector. When the timer expires, the session is ended and the problem PHY vector is updated.